﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <string.h>
// 原题连接：https://leetcode.cn/problems/longest-common-prefix/
// 题目描述：
/*
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
*/

// 方法1：横向扫描
/*
思路：
依次遍历每个字符串，更新最长公共前缀。
因为是所有字符串的最长公共前缀，所以在求出第一个和第二个字符串的最长公共前缀之后，
在后面的比较中，这个公共前缀的长度只有可能减小，而不可能再增加。
所以我们可以先把第一和第二个字符串的最长公共前缀保存起来，在下面的比较中，
只需要拿保存好的公共前缀进行比较即可。
*/
char longest_prefix[200] = { 0 }; // 用来保存最长公共前缀
char* longestCommonPrefix1(char** strs, int strsSize) {
	// 先求出第一和第二个字符串的最长公共前缀
	int i = 0;
	if (strs[0][0] != strs[1][0]) {
		return "";
	}
	while (strs[0][i] && strs[1][i]) {
		if (strs[0][i] == strs[1][i]) {
			strs[0][i] = strs[0][i]; 
			i++;
		}
		else {
			break;
		}
	}
	longest_prefix[i] = '\0'; // 加上字符串结束标志
	// 在进行后面的比较
	for (i = 2; i < strsSize; i++) {
		if (longest_prefix[0] != strs[i][0]) {
			return "";
		}
		int max_len = 0;
		while (longest_prefix[max_len] && strs[i][max_len]) {
			if (longest_prefix[max_len] == strs[i][max_len]) {
				max_len++;
			}
			else {
				break;
			}
		}
		longest_prefix[max_len] = '\0'; // 更新最长前缀
	}
	return longest_prefix;
}

// 方法2：纵向扫描法
/*
思路：
即从前往后遍历每一个字符串的每一列，比较相同列上的字符是否相同，
如果相同则继续对下一列进行比较，如果不相同则但前列不再属于公共前缀，
当前列之前的部分为最长公共前缀。
*/

char* longestCommonPrefix2(char** strs, int strsSize) {
	int max_len = 0; // 用来记录最长公共前缀的长度
	int i = 0;
	while (1) {
		for (i = 0; i < strsSize - 1; i++) {
			if ((strs[i][max_len] && strs[i + 1][max_len]) && (strs[i][max_len] == strs[i + 1][max_len])) {
				;
			}
			else {
				if (0 == max_len) {
					return "";
				}
				break;
			}
		}
		if (i == strsSize - 1) {
			max_len++;
		}
		else {
			break;
		}
	}
	for (i = 0; i < max_len; i++) {
		longest_prefix[i] = strs[0][i];
	}
	longest_prefix[max_len] = '\0';
	return longest_prefix;
}


int main() {
	char* arr[3] = { "doge","dogeabcd","dogeabcdef" };
	char *pc = longestCommonPrefix2(arr, 3);
	printf("%s\n", pc);
	return 0;
}